package com.kevin.Code.Array;

/**
 * @author Vinlee Xiao
 * @Classname SingleElementInaSortedArray
 * @Description Leetcode 540. 有序数组中的单一元素 中等难度 思路不够好
 * @Date 2022/2/19 19:09
 * @Version 1.0
 */
public class SingleElementInaSortedArray {

    /**
     * 自己思路
     * 思路一：异或运算 时间复杂度O(n)
     * 思路二：二分法O(logn)
     *
     * @param nums
     * @return
     */
    public int singleNonDuplicate(int[] nums) {
        int result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            result = result ^ nums[i];
        }
        return result;
    }

    /**
     * 二分法
     * 根据代码特点
     *
     * @param nums
     * @return
     */
    public int singleNonDuplicate1(int[] nums) {
        int length = nums.length;
        int low = 0;
        int high = length - 1;
        int mid = 0;
        while (low < high) {
            //去中点
            mid = (low + high) >> 1;
            //mid^1  用来判断是否是偶数 如果mid^1 == mid 说明是偶数
            //mid^1 != mid 说明是奇数
            if (mid > 1 && mid < length - 1 && nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) {
                return nums[mid];
            }
            if (nums[mid] == nums[mid ^ 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return nums[low];
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 2, 3, 3};
        SingleElementInaSortedArray singleElementInaSortedArray = new SingleElementInaSortedArray();
        int i = singleElementInaSortedArray.singleNonDuplicate1(nums);
        System.out.println(i);
    }

}
